def RAND(item, stacks, rng):
    """Completely random placement heuristic."""
    return rng.choice(stacks)
    
    
def CM(item, stacks, rng):
    """Conflict minimization strategy. Items are placed in a random stack where they do not 
    cause new inversions, if possible. If an inversion is unavoidable, a stack is randomly 
    selected from all available stacks."""
    RCL = [s for s in stacks if not s.creates_inversion(item)]
    return rng.choice(RCL if len(RCL) > 0 else stacks)
    
    
def ProbFO(prob_fnc, name=None):
    """A heuristic factory that uses the Flexibility Optimization principle to create a sorted 
    list of stacks, and then selects the target stack from this list using a probabilistic function
    'prob_fnc'. 'prob_fnc' should receive a single argument (an rng) and return a value between 0 
    and 1, with 1 representing the greediest choice (FO-wise)."""
    def heuristic(item, stacks, rng):
        noise = rng.random
        scored_stacks = sorted((FO_score(item, s), noise(), s) for s in stacks)
        index = int(round((len(stacks) - 1) * prob_fnc(rng)))
        return scored_stacks[index][-1]
    heuristic.__name__ = "ProbFO(%s)" % prob_fnc.__name__ if name is None else name
    return heuristic
    
    
def FO_score(item, stack):
    """Auxiliary stack scoring function used by FO-based placement heuristics. This function 
    assigns values in the range [0, 1] for non-inversion moves, with score equal to 1 for moves 
    where no stack flexibility is lost, and 0 is assigned to moves which put any item in an empty
    stack (infinite loss of flexibility). Inversion moves have values in the range [-1, 0[, and 
    the lower values are assigned to moves where the difference between the item's due date and 
    the stack's earliest due date is biggest."""
    item_due  = item.due
    stack_due = stack.earliest_due
    if item_due is None:     # item will not leave the warehouse within the planning horizon
        return +1.0 if stack_due is None else -1.0
    elif stack_due is None:  # stack is empty or only has items that will not leave
        return 0.0
    else:
        overlap = item_due.intersection(stack_due)
        # overlap between item due and stack due
        if overlap is not None:
            try:
                return 0.5 + 0.5 * overlap.size / stack_due.size
            except ZeroDivisionError:
                return 1.0
        # item is delivered before stack due starts    
        if item_due.end < stack_due.start:
            return 0.5 * item_due.end / stack_due.start
        # item can only be delivered after stack due ends (inversion)
        if stack_due.end < item_due.start:
            return 1.0 / (1.0 + item_due.start - stack_due.end) - 1.0
        raise Exception("OOPS! something went terribly wrong somewhere...")
        
        
FO  = ProbFO(lambda rng: 1.0, name="FO")
PFO = ProbFO(lambda rng: rng.uniform(0.9, 1.0), name="PFO<0.9+>")
